Mobile devices are mostly computational complexity sensitive because of the limited computing resource. The BandWidth Extension (BWE) algorithm in audio codec standard of China for mobile communication named AVS P10 was proposed to improve the mobile audio quality, but the computational complexity of the algorithm is too high to implement in mobile devices. The original BWE algorithm processes was analyzed, and the main reason of high computational complexity was identified to be the frequently usage of time-frequency transformation. Based on the analysis, a computational complexity optimization scheme was proposed, which include algorithm optimization and code optimization. The complexity of the algorithm was reduced by reducing the call number of Fast Fourier Transform (FFT). And the time consumption of the algorithm was reduced by some methods, such as sacrificing memory space for speed.The experimental results show that computation time consumption ratio of BWE module in encoder and decoder are decreased by 4.5 and 14.3 percentage points respectively, without reducing the overall audio codec subjective quality; the computational complexity of the algorithm is significantly reduced, which is beneficial to the application of the coding and decoding algorithm in the field of mobile audio.